#include <vector>
#include <iostream>
using namespace std;

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        std::vector<int>::iterator it = nums.begin();
        while ((it+1) != nums.end()) {
            if (*it == *(it + 1)) {
                it = nums.erase(it + 1);
            }
            else {
                ++it;
            }
        }
        return nums.size();
    }
};

void test()
{
    vector<int> v;
    v.push_back(1); 
    v.push_back(2); 
    v.push_back(2); 
    v.push_back(3); 
    v.push_back(4);
    v.push_back(4);
    v.push_back(5);
    v.push_back(7);
    v.push_back(8);
    v.push_back(8);
    //cout << Solution().removeDuplicates(v) << endl;
    vector<int>::iterator it = v.begin();
    while (it != v.end())
    {
        if(*it %2 == 0)
            it = v.erase(it);
        cout << *it << " ";
        ++it;
    }

    vector<int> v2(v.size());
    vector<int> v3(v.size(), 100);

    cout << endl;
}


int test2()
{
    // constructors used in the same order as described above:
    std::vector<int> first;                                // empty vector of ints
    std::vector<int> second(4, 100);                       // four ints with value 100
    std::vector<int> third(second.begin(), second.end());  // iterating through second
    std::vector<int> fourth(third);                       // a copy of third

    // the iterator constructor can also be used to construct from arrays:
    int myints[] = { 16,2,77,29 };
    std::vector<int> fifth(myints, myints + sizeof(myints) / sizeof(int));

    std::cout << "The contents of fifth are:";
    for (std::vector<int>::iterator it = fifth.begin(); it != fifth.end(); ++it)
        std::cout << ' ' << *it;
    std::cout << '\n';

    return 0;
}


int MoreThanHalfNum_Solution(vector<int>& numbers) {
    vector<int> v(10001, 0);
    std::vector<int>::iterator it = numbers.begin();
    while (it != numbers.end())
    {
        v[*it]++;
        ++it;
    }
    int maxi = 0;
    for (int i = 1; i < v.size(); ++i)
    {
        if (v[i] > v[maxi])
        {
            maxi = i;
        }
    }
    return maxi;
}

int t()
{
    vector<int> v;
    v.push_back(9);
   /* v.push_back(1);
    v.push_back(2);
    v.push_back(2);
    v.push_back(2);
    v.push_back(2);
    v.push_back(3);
    v.push_back(3);
    v.push_back(3);
    v.push_back(4);
    v.push_back(5);
    v.push_back(5);
    v.push_back(5);
    v.push_back(5);
    v.push_back(5);
    v.push_back(5);
    v.push_back(5);
    v.push_back(5);
    v.push_back(5);
    v.push_back(5);
    v.push_back(5);*/
    cout << MoreThanHalfNum_Solution(v);

    return 0;
}

int main()
{
    class Solution {
    public:
        string tmp;
        vector<string> res;
        vector<string> board = { "","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz" };
        void DFS(int pos, string digits) {
            if (pos == digits.size()) {
                res.push_back(tmp);
                return;
            }
            int num = digits[pos] - '0';
            for (int i = 0; i < board[num].size(); i++) {
                tmp.push_back(board[num][i]);
                DFS(pos + 1, digits);
                tmp.pop_back();
            }
        }
        vector<string> letterCombinations(string digits) {
            if (digits.size() == 0) return res;
            DFS(0, digits);
            return res;
        }
    };
    return 0;
}